解鎖二元樹的魔法：遞迴與迭代的雙重奏！

當你看到二元樹（Binary Tree）這個詞時，是不是有點「哇～好複雜喔」的感覺呢？

別擔心！今天我們要解的是一個經典的題目：Binary Tree Inorder Traversal，這是 LeetCode 上一道基本但非常實用的題目。

如果你對二元樹有點陌生也沒關係，因為透過這題，我們會一起把這個概念解得清清楚楚，打通「左 -> 根 -> 右」這個中序遍歷的小任督二脈，讓你在二元樹的世界裡不再迷路！

這題不僅是演算法學習的基礎，還會在各種應用場景中頻頻遇到，比如遍歷檔案結構、計算表達式的樹狀結構等等。

我們今天就用 TypeScript 來實作這個小任務，保證讓你看完後收穫滿滿，信心倍增！準備好了嗎？
Let's dive in!

英文題目 Binary Tree Inorder Traversal

Given the root of a binary tree, return the inorder traversal of its nodes' values.
給定一個二元樹的根節點 root，返回其節點值的中序遍歷。

Example 1:

Input: root = [1,null,2,3]

Output: [1,3,2]

Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [4,2,6,5,7,1,3,9,8]

Explanation:

Example 3:

Input: root = []

Output: []

Example 4:

Input: root = [1]

Output: [1]

解題思路：

嘿嘿！今天我們來聊聊二元樹的中序遍歷吧！
中序遍歷的順序是「左 -> 根 -> 右」，換句話說，我們會先訪問左子樹，再訪問根節點，最後才訪問右子樹。
這在樹結構的各種應用中非常常見。

那麼具體該怎麼做呢？我們就一起來拆解這個問題吧！

解題脈絡：

1. 理解中序遍歷：

   • 中序遍歷是指先遍歷左子樹，再訪問根節點，最後遍歷右子樹。舉例來說，如果樹的結構是 [1,null,2,3]，那麼中序遍歷的結果就是 [1,3,2]。

2. 實現方法：

   • 我們有兩種主要的方式來解決這個問題：遞迴 和 迭代。
   • 遞迴方法較為直觀，容易理解：我們一直呼叫自身，直到沒有節點可遍歷。
   • 迭代方法稍微複雜一點，但可以避免遞迴深度過深的問題。主要透過堆疊來實現這個流程，按順序將節點壓入和彈出堆疊。

3. 步驟分解：

   • 步驟 1：檢查節點是否存在。
     如果節點不存在，直接返回空陣列。
   • 步驟 2：定義遞迴函數（或使用迭代的堆疊方法）。
     使用遞迴的方式去遍歷左子樹，再處理根節點，最後遍歷右子樹。
   • 步驟 3：返回結果。
     按照中序遍歷的順序將結果儲存並輸出。

本次要點：

• 知識點： 二元樹結構、遞迴基礎、堆疊結構。
• 小技巧： 遞迴雖然好用，但記得控制深度；如果出現「爆堆疊」的情況，就要考慮使用迭代法囉！

實作

來看看實作的部分吧！

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val);
        this.left = (left===undefined ? null : left);
        this.right = (right===undefined ? null : right);
    }
}

// 遞迴解法
function inorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];
    const traverse = (node: TreeNode | null) => {
        if (!node) return;
        traverse(node.left); // 先處理左子樹
        result.push(node.val); // 處理根節點
        traverse(node.right); // 處理右子樹
    };
    traverse(root);
    return result;
}

// 迭代解法
function inorderTraversalIterative(root: TreeNode | null): number[] {
    const result: number[] = [];
    const stack: (TreeNode | null)[] = [];
    let current: TreeNode | null = root;

    while (current || stack.length) {
        // 一直深入左子樹並壓入堆疊
        while (current) {
            stack.push(current);
            current = current.left;
        }
        // 當左子樹到底時，處理堆疊中的節點
        current = stack.pop()!;
        result.push(current.val);
        // 處理右子樹
        current = current.right;
    }

    return result;
}

重點小結：

• 遞迴解法：

  • 簡單易懂：程式碼簡潔，直接呼叫自身進行中序遍歷。
  • 適合小樹：對於節點數量較少的樹結構，遞迴方法效率高且容易實現。

• 迭代解法：

  • 更通用的方案：利用堆疊實現，避免遞迴深度過深的問題，適合更複雜的應用。
  • 適合大規模樹：能夠處理大量節點而不會爆堆疊，適合更大範圍的資料結構。

這段程式碼兩個解法各有千秋！
無論選擇哪種方式，都能輕鬆搞定中序遍歷。

希望大家看完後能夠更熟悉二元樹的操作囉～(●'▿'●)💞